﻿// 0818train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

/*
示例
{0,0,2},
{1,3,4},
{6,6,4}

明文"0 3",密文"0 1 1 1"

输入
第一行输入1个正整数N，代表明文的长度(1 <= N <= 9)
第二行输入N个明文数字组成的序列Data[i](整数，0 <= Data[i] <= 9)
第三行输入1个正整数M，(1 <= M <= 9)
接下来输入一个M*M的矩阵代表密码本Book[i][i]，(整数，0 <= Book[i][i] <= 9)

输出
如明文 第i位Data[i]对应密码本单元格为Book[i][j]，
则明文第i位对应的密文为X Y，X和Y之间用空格隔开。
如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"

示例1
输入
2
0 3
3
0 0 2
1 3 4
6 6 4

输出
0 1 1 1
 */

class Solution01
{
public:
    int row_size, col_size;
    vector<int>track_target_vec; //目标，不可改
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
    //------
    //可变区
    vector<pair<int, int>>track_vec; //回溯专用，可改
    int track_index = 0;
    bool is_find = false;
    vector<pair<int, int>>result_vec;
    void backTrack(vector<vector<int>>& grid, vector<vector<bool>>&checked, int prev_r, int prev_c)
    {
        if (track_index==track_target_vec.size())
        {
            is_find = true;
            result_vec = track_vec;
            return;
        }

        for (auto&dir_vec: DirectionGrid)
        {
            int curr_r = prev_r + dir_vec[0];
            int curr_c = prev_c + dir_vec[1];

            //未越界，未访问，等于track_target_vec[track_index]
            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (is_curr_r&&is_curr_c)
            {
                bool is_visited = checked[curr_r][curr_c];
                int curr_value = grid[curr_r][curr_c];
                bool is_available = curr_value == track_target_vec[track_index];
                if (!is_visited && is_available)
                {
                    //做选择
                    track_vec.push_back(make_pair(curr_r, curr_c));
                    track_index++;
                    checked[curr_r][curr_c] = true;
                    //回溯
                    backTrack(grid, checked, curr_r, curr_c);
                    //撤销选择
                    track_vec.pop_back();
                    track_index--;
                    checked[curr_r][curr_c] = false;
                }

            }

        }

        //backTrack
    }
    void solve01(vector<vector<int>>&grid, vector<int>&target_vec)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        track_target_vec = target_vec;

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                if (grid[r][c]==track_target_vec[track_index])
                {
                    //做选择
                    track_vec.push_back(make_pair(r, c));
                    track_index++;
                    checked[r][c] = true;
                    //回溯
                    backTrack(grid, checked, r, c);
                    //撤销选择
                    track_vec.pop_back();
                    track_index--;
                    checked[r][c] = false;
                }

                if (is_find)
                {
                    for (auto&oh_pair: result_vec)
                    {
                        cout << oh_pair.first << ' ' << oh_pair.second << ' ';
                    }

                    return;
                }

            }

        }
        cout << "error";
        //solve01
    }

    //Solution01
};


/*
 给定M (0<M<=30)个字符(a-z)，从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串，
 要求相同的字符不能相邻，
 计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回0。

输入描述
给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述
满足条件的字符串个数

示例1
输入
abc 1
输出
3
给定的字符为abc，结果字符串长度为1，可以拼接成a,b,c，共3种

示例2
输入
aabc 3
输出
8
 */

class Solution02
{
public:
    int target_track_size;
    //可变区
    vector<char>track_str_vec;
    vector<vector<char>>cache_vec;
    int result = 0;
    void backTrack(vector<char>&origin_str, vector<bool>&used)
    {
        //记录满足条件的子集
        if (track_str_vec.size()== target_track_size)
        {
            cache_vec.push_back(track_str_vec);
            result++;
            return;
        }

        for (int i=0; i<origin_str.size(); i++)
        {
            if (used[i]) continue;

            if (i > 0 && origin_str[i] == origin_str[i - 1] && !used[i - 1])
                continue;

            if (track_str_vec.size()>0)
            {
                char last_track_char = track_str_vec[track_str_vec.size() - 1];
                if (origin_str[i] == last_track_char)
                	continue;
            }
            

            //做选择
            track_str_vec.push_back(origin_str[i]);
            used[i] = true;
            //回溯
            backTrack(origin_str, used);
            //撤销选择
            track_str_vec.pop_back();
            used[i] = false;
        }
	    
    }
    void solve02(string&origin_str, int sub_size)
    {
        target_track_size = sub_size;
        int str_size = origin_str.size();
        
        vector<bool>used(str_size, false);

        vector<char>origin_str_vec;
        for (auto&oh_char:origin_str)
        {
            origin_str_vec.push_back(oh_char);
        }

        sort(origin_str_vec.begin(), origin_str_vec.end());

        backTrack(origin_str_vec, used);

        //for (auto&char_vec: cache_vec)
        //{
        //    string str = "";
        //    for (auto&oh_char:char_vec)
        //    {
        //        str += oh_char;
        //    }
        //    cout << str << endl;
        //}

        cout << result;
        //solve02
    }

};


int main()
{
	{
        //aabc 3
        //xxtdcchtemmjmwkaiknpjngagxe 2 210
        string str = "gmgcaz";
        int target_size = 1;
        //string str;
        //int target_size;
        //cin >> str >> target_size;
        Solution02 solu;
        solu.solve02(str, target_size);

        return 0;
	}


/*
2
0 3
3
0 0 2
1 3 4
6 6 4
 */
    //solve01(vector<vector<int>>&grid, vector<int>&target_vec)
    //vector<vector<int>>grid = {{0,0,2},{1,3,4},{6,6,4}};
    //vector<int>target_vec = {0,3};
    int target_size;
    cin >> target_size;
    vector<int>target_vec(target_size);
    for (int i=0; i<target_size; i++)
    {
        cin >> target_vec[i];
    }

    int grid_size;
    cin >> grid_size;
    vector<vector<int>>grid(grid_size, vector<int>(grid_size));

    for (int r=0; r<grid_size; r++)
    {
        for (int c=0; c<grid_size; c++)
        {
            cin >> grid[r][c];
        }
    }

    Solution01 solu;
    solu.solve01(grid, target_vec);

    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
